package 归并排序;

public class Solution51 {
    public static void main(String[] args) {
        int[] nums = {7,5,6,4};
        System.out.println(reversePairs(nums));
    }

    public static int reversePairs(int[] nums) {
        //先写递归
        return process(nums, 0, nums.length - 1);
    }

    public static int process(int[] nums, int l, int r) {
        //base case
        if (l == r) {
            return 0;
        }
        int mid = l + ((r - l) >> 1);
        //左排序
        int left = process(nums, l, mid);
        //右排序
        int right = process(nums, mid + 1, r);
        //merge
        int mer = merge(nums, l, mid, r);
        return left + right + mer;
    }

    public static int merge(int[] nums, int l, int mid, int r) {
        int[] help = new int[r - l + 1];
        int i = 0;
        int p1 = mid;
        int p2 = r;
        int res = 0;
        //边界条件
        while (p1 >= l && p2 >= mid + 1) {
            res = res + (nums[p1] > nums[p2] ? (p1-mid) : 0);
            help[i++] = nums[p1] > nums[p2] ? nums[p2--] : nums[p1--];
        }
        while (p1 >= l) {
            help[i++] = nums[p1--];
        }

        while (p2 >= mid + 1) {
            help[i++] = nums[p2--];
        }
        System.out.println(res);

        return res;
    }

}

